class Solution:
    def solve(self, board) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return
        status = [[1 for y in range(len(board[x]))] for x in range(len(board))]
        not_change = set()
        for i in range(len(board)):
            if i == 0 or i == len(board) - 1:
                for j in range(len(board[i])):
                    if board[i][j] == 'O':
                        status[i][j] = 0
                        not_change.add((i, j))
            else:
                for j in [0, len(board[i]) - 1]:
                    if board[i][j] == 'O':
                        status[i][j] = 0
                        not_change.add((i, j))
        max_x = len(board)
        max_y = len(board[0])
        while len(not_change) > 0:
            tmp = set()
            for xy in not_change:
                x, y = xy
                for i, j in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
                    if 0 <= i < max_x and 0 <= j < max_y:
                        if status[i][j] == 1 and board[i][j] == 'O':
                            status[i][j] = 0
                            tmp.add((i, j))
            not_change = tmp

        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'O' and status[i][j] == 1:
                    board[i][j] = 'X'


if __name__ == '__main__':
    so = Solution()
    board = """
X X X X
X O O X
X X O X
X O X X
    """.replace(" ", '').splitlines()
    board.pop(0)
    board = [[y for y in x] for x in board]
    so.solve(board)
    print(board)
